package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Problem119B {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int t = 18;
		//here max = 10^t
		List<BigInteger> ns = new ArrayList<BigInteger>();
		for (int b = 2; b < t*Math.log(10)/Math.log(2)+1; b ++) {
			//   a^b = a1...an
			//=> (9n)^b >= (a1+...+an)^b = a1...an >= 10^(n-1)
			// so k = max {n: (9n)^b >= 10^(n-1)}
			int k = 1;
			while (Math.pow(9*k, b) >= Math.pow(10, k-1)) k ++;
			// a^b <= max => a <= max^(1/b)
			for (int a = 2; a < Math.min(Math.pow(10, k), Math.pow(10, t*1.0/b)); a ++) {
				BigInteger y = BigInteger.valueOf(a).pow(b);
				String s = y.toString();
				char[] cs = s.toCharArray();
				int x = 0;
				for (char c: cs) {
					x += c-'0';
				}
				if (x == a) {
					ns.add(y);
					System.out.println(a + "^" + b + "=" + s);
				}
			}
		}
		
		BigInteger[] E = ns.toArray(new BigInteger[ns.size()]);
		Arrays.sort(E);
		System.out.println(E.length);
		System.out.println("E(30)=" + E[29]);
	}

}
